#define M         6
#define DEGREE    M / 2
using KEY_VALUE = int;

#include <stdlib.h>

struct B_tree_node {
	KEY_VALUE* keys;
	struct B_tree_node** childrens;
	int num;
	int leaf;
};

struct B_tree {
	struct B_tree_node* root;
};

B_tree_node* create_node(int leaf) {
	B_tree_node* node = (B_tree_node*)malloc(sizeof(B_tree_node));
	if (!node) {
		return nullptr;
	}
	int t = DEGREE;
	node->keys = (KEY_VALUE*)malloc((2 * t - 1) * sizeof(KEY_VALUE));
	node->childrens = (B_tree_node**)malloc(2 * t * sizeof(B_tree_node*));
	if (!node->keys || !node->childrens) {
		free(node->keys);
		free(node->childrens);
		free(node);
		return nullptr;
	}
	node->num = 0;
	node->leaf = leaf;
	return node;
}

void B_tree_insert(B_tree* T, KEY_VALUE k) {
	if (!T->root) {
		T->root = create_node(1);
		T->root->keys[0] = k;
		T->root->num = 1;
		return;
	}
	B_tree_node* root = T->root;
	if (root->num == M - 1) {
		B_tree_node* new_root = create_node(0);
		new_root->childrens[0] = root;
		B_tree_split(T, new_root, 0);
		T->root = new_root;
		B_tree_add(T, new_root, k);
	}
	else {
		B_tree_add(T, root, k);
	}
}

void B_tree_split(B_tree* T, B_tree_node* x, int i) {

	struct B_tree_node* y = x->childrens[i];
	struct B_tree_node* z = create_node(y->leaf);
	if (!z) return;
	
	int t = DEGREE;

	for (int j = 0; j < t - 1; ++j) {
		z->keys[j] = y->keys[j + t];
	}

	if (x->leaf == false) {
		for (int j = 0; j < t; ++j) {
			z->childrens[j] = y->childrens[j + t];
		}
	}

	y->num = t - 1;

	for (int j = x->num; j > i; j--) {
		x->childrens[j + 1] = x->childrens[j];
	}

	for (int j = x->num - 1; j >= i; j--) {
		x->keys[j + 1] = x->keys[j];
	}
	x->keys[i] = y->keys[t - 1];
	x->childrens[i + 1] = z;
	x->num++;
}

void B_tree_add(B_tree* T, B_tree_node* x, KEY_VALUE k) {
	int i = x->num - 1;
	if (x->leaf == true) {
		while (i >= 0 && x->keys[i] > k) {
			x->keys[i + 1] = x->keys[i];
			i--;
		}
		x->keys[i + 1] = k;
		x->num++;
	}
	else {
		while (i >= 0 && x->keys[i] > k) i--;
		if (x->childrens[i + 1]->num == M - 1) {
			B_tree_split(T, x, i + 1);
			if (x->keys[i] < k) ++i;
		}
		B_tree_add(T, x->childrens[i + 1], k);
	}
}

